package leetcode_day._2021._202104._2131;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/28 8:58
 * 平方数之和
 * 是否存在两个整数 a, b; 使得 a * a + b * b = c
 * 之前动态规划有做过一题，完全平方数，求使用最少的完全平方数组成目标数，这个方法在这题中
 * 相当于暴力解法，不可取
 * 双指针
 * 假设 a <= b
 * a * a + b * b == c true
 * a * a + b * b > c , b--
 * a * a + b * b < c , a++
 */
public class _28_633 {
    public static void main(String[] args) {
    }

    public boolean judgeSquareSum(int c) {
//        for (long a = 0; a * a <= c; a++) {
//            double b = Math.sqrt(c - a * a);
//            if (b == (int) b) return true;
//        }
//        return false;
        int a = 0, b = (int) Math.sqrt(c);
        while (a <= b) {
            int tmp = a * a + b * b;
            if (tmp == c) return true;
            if (tmp > c) b--;
            else a++;
        }
        return false;
    }
}
